#include <iostream>
#include <vector>

using namespace std;

// https://leetcode.cn/problems/maximize-the-number-of-target-nodes-after-connecting-trees-i/description/?envType=daily-question&envId=2025-05-28
// 3372. 连接两棵树后最大目标节点数目 I

class Solution
{
public:
    vector<vector<int>> dealNode(vector<vector<int>> &edges)
    {
        vector<vector<int>> ans(edges.size() + 1);
        for (const auto &it : edges)
        {
            ans[it[0]].push_back(it[1]);
            ans[it[1]].push_back(it[0]);
        }
        return ans;
    }
    int dfs(vector<vector<int>> &tree, int index, int k, int pre)
    {
        if (tree[index].empty() || k <= 0)
        {
            return 1;
        }
        int ans = 1;
        for (auto node : tree[index])
        {
            if (node != pre)
            {
                ans += dfs(tree, node, k - 1, index);
            }
        }
        return ans;
    }
    vector<int> maxTargetNodes(vector<vector<int>> &edges1, vector<vector<int>> &edges2, int k)
    {
        vector<vector<int>> tree1 = dealNode(edges1);
        vector<vector<int>> tree2 = dealNode(edges2);

        int max2 = (k == 0 ? 0 :1);
        if (k > 1)
        {
            for (int i = 0; i < tree2.size(); i++)
            {
                max2 = max(max2, dfs(tree2, i, k - 1, -1));
            }
        }
        vector<int> ans(tree1.size());
        for (int i = 0; i < tree1.size(); i++)
        {
            ans[i] = dfs(tree1, i, k, -1) + max2;
        }
        return ans;
    }
};

int main()
{
    return 0;
}
